剑指 Offer 32 - I. 从上到下打印二叉树

题目描述

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

1
2
3
4
5
3  
    / \
   4  5
  / \
 1   2

给定的树 B:

1
2
3
   4   
  /
 1

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

1
2
输入:A = [1,2,3], B = [3,1]
输出:false

示例 2:

1
2
输入:A = [3,4,5,1,2], B = [4,1]
输出:true

限制:

$0 <= 节点个数 <= 10000$


算法

(DFS,暴力遍历) $O(nm)$

算法步骤:

  1. 遍历树 $root$ 中的每个节点 $s$ 都与子树 $subRoot$ 进行匹配
  2. 递归匹配子树 $s$ 和 $subRoot$ 中的每个节点,如果每个节点都相同,则匹配成功。

边界:

  1. isSubStructure() 中如果 $subRoot$ 为空,题目已知空树不是任何树的子结构,所以返回 $false$。
  2. dfs() 中,当 $q$ 为空时不需要判断 $p$ 是否为空,只要保证 $q$ 是 $p$ 的子结构即可,不需要完全匹配。

时间复杂度

树 $root$ 中的每个节点都需要与子树 $subRoot$ 进行匹配,所以时间复杂度为 $O(nm)$,$n$ 为 $root$ 的节点个数,$m$ 为 $subRoot$ 的节点个数。

空间复杂度

一次匹配时最多需要 $O(max(d_1, d_2))$ 的空间复杂度,$d_1$ 表示 $root$ 的子树匹配结束时的深度,$d_2$ 表示 $subRoot$ 匹配结束时的深度。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* p, TreeNode* q) {
if (!q) return true;
if (!p || p->val != q->val) return false;
return dfs(p->left, q->left) && dfs(p->right, q->right);
}

bool isSubStructure(TreeNode* root, TreeNode* subRoot) {
if (!root || !subRoot) return false;
if (dfs(root, subRoot)) return true;
return isSubStructure(root->left, subRoot) || isSubStructure(root->right, subRoot);
}
};
Author: tonngw
Link: https://tonngw.com/2022/07/08/剑指 Offer/剑指 Offer 32 - I. 从上到下打印二叉树/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.